package Sort2;

import java.util.Arrays;

/**
 * @author galaxy
 * @date 2022/03/20 13:15
 **/
public class SevenSort {
    public static void selectionSort(int[] arr){
        //无序区间[0...n] 有序区间[ ]
        //优化1：arr.length-1 当无序区间只剩下一个元素时，无需再次进行排序
        for (int i = 0; i < arr.length-1; i++) {
            //min存储了当前最小值的索引
            int min=i;
            //从盛夏的元素中选择最小值
            for (int j = i+1; j < arr.length; j++) {
                if(arr[j]<arr[min]){
                    min=j;
                }
            }
            //min这个索引一定对应了当前无序区间最小值的索引
            swap(arr,min,i);
        }
    }
    public static void selectionSortOP(int[] arr){
        int low=0;
        int high=arr.length-1;
        //low=high ,无序区间只剩下一个元素，此时整个数组已经有序
        while(low<high){
            int min=low;
            int max=low;
            for (int i = low+1; i <=high ; i++) {
                if(arr[i]<arr[min]){
                    min=i;
                }
                if(arr[i]>arr[max]){
                    max=i;
                }
                //此时min和max分别对应最小和最大元素的下标
            }
            swap(arr,low,min);
            if(max==low){
                //最大值已经被换到min这个位置
                max=min;
            }
            swap(arr,max,high);
            low+=1;
            high-=1;
        }
    }

    /**
     * 直接插入排序
     * 每次直接将无序区间中的第一个值插入到已经排序区间的合适位置，直到整个数组有序
     * @param arr
     */
    public static void insertionSort(int[] arr){
        //已排序区间[o,i)  无序区间[i,n]
        for (int i = 1; i < arr.length ; i++) {
            //待排序区间的第一个元素arr[i] 从待排序区间额第一个元素向前看，找到合适的插入位置
//            for (int j = i; j>0 ; j--) {
//                //arr[j]待排序区间的第一个元素  arr[j-1]已排序区间的最后一个元素
//                if(arr[j]>=arr[j-1]){
//                    //已经有序，直接下次循环 稳定性
//                    break;
//                }else {
//                    swap(arr,j,j-1);
//                }
//            }
            for (int j = i; j >0&&arr[j]<arr[j-1] ; j--) {
                swap(arr,j,j-1);
            }
        }
    }
    public static void insertionSortBS(int[] arr){
        //有序区间[0,i) 无序区间[i,n]
        for (int i = 1; i < arr.length; i++) {
            int val=arr[i];
            int left=0;
            int right=i;
            while (left<right){
                int mid=left+((right-left)>>1);
                if(arr[i]<arr[mid]){
                    right=mid;
                }else {
                    left=mid+1;
                }
            }
            for (int j = i; j>left ; j--) {
                arr[j]=arr[j-1];
            }
            arr[left]=val;
        }
    }
    private static void swap(int[] arr, int i, int j) {
        int temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }

    public static void main(String[] args) {
        int[] arr={3,4,7,2,6,9,5,1,};
        selectionSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

